/*
 * @lc app=leetcode.cn id=1103 lang=cpp
 *
 * [1103] 分糖果 II
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<int> distributeCandies(int candies, int num_people)
    {
        /**
         * 假设一共有 n 个孩子，c个糖果
         * 假设需要一共分了 x 轮，则，前（x-1）轮，每轮发出去的糖果数目分别为
         * 1/2(n(n+1)), 1/2(n(3n+1)), 1/2(n(5n+1)), ..., 1/2(n( (2(x-1)-1)n+1 ))
         *
         * 第x轮至少发放了1颗糖果，最多发放了 1/2(n( (2x-1)n+1))
         *
         * 前 x-1 轮总计发放的糖果数量为
         * 1/2(n(  (x-1)^2 n + (x-1) ))
         * 则有数学方程
         * 1/2(n(  (x-1)^2 n + (x-1) )) <= c
         * 1/2(n(  (x)^2 n + (x) )) >= c
         * 解得 sqrt(8c+1) / (2n) <= x <= 1 + sqrt(8c+1) / (2n)
         *
         * 设 i 表示第 i 个孩子 （序号从0开始计数）
         * 那么前 （x-1）轮一共拿到的糖果数量是
         * (x-2)(x-1) * n / 2 + (x-1)(i+1)
         *
         * 第 x 轮，第 i 个孩子 最多分到的糖果数量是
         * (x-1)n + (i+1)
         */
        const long long n = num_people;
        long long c = candies;

        vector<int> ans(num_people, 0);
        if (c == 0)
        {
            return ans;
        }

        long long x = 1 + sqrt(8 * c + 1) / (2 * n);
        if (((x - 1) * (x - 1) * n + (x - 1)) * n / 2 > c)
            x--;

        for (long long i = 0; i < n; i++)
        {
            ans[i] = n * (x - 2) * (x - 1) / 2 + (x - 1) * (i + 1);
        }

        c -= ((x - 1) * (x - 1) * n + (x - 1)) * n / 2;
        for (long long i = 0; i < n && c; i++)
        {
            long long tmp = min((x - 1) * n + i + 1, c);
            ans[i] += tmp;
            c -= tmp;
        }

        return ans;
    }
};
// @lc code=end
